#include <iostream>
#include "BinaryTree.h"
using namespace std;

    // Test program
int main( )
{
    BinarySearchTree<int> tr1;
    int NUMS1 = 410;
    const int GAP1  =  3771;
    int i;

    cout << "(BinarySearchTree)Checking... (no more output means success)" << endl;

    for( i = GAP1; i != 0; i = ( i + GAP1 ) % NUMS1 )
        tr1.insert( i );

    for( i = 1; i < NUMS1; i+= 2 )
        tr1.remove( i );    //删除奇数
        tr1.remove(GAP1);

        if(NUMS1<=40)tr1.printTree( );
        cout<<endl;
    if( tr1.findMin( ) != 2 || tr1.findMax( ) != NUMS1 - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 2; i < NUMS1; i+=2 )
        if( !tr1.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS1; i+=2 )
    {
        if( tr1.contains( i ) )
            cout << "Find error2!" << endl;
    }

    BinarySearchTree<int> tr2;
    tr2 = tr1;

    for( i = 2; i < NUMS1; i+=2 )
        if( !tr2.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS1; i+=2 )
    {
        if( tr2.contains( i ) )
            cout << "Find error2!" << endl;
    }

    cout << "Finished testing" << endl;
        SplayTree<int> tr3;
        int NUMS2 = 30000;
        const int GAP2  =   37;

        cout << "(Splaytree)Checking... (no more output means success)" << endl;

        for( i = GAP2; i != 0; i = ( i + GAP2 ) % NUMS2 )
            tr3.insert( i );

        for( i = 1; i < NUMS2; i+= 2 )
            tr3.remove( i );

        if( NUMS2 < 40 )
            tr3.printTree( );
        if( tr3.findMin( ) != 2 || tr3.findMax( ) != NUMS2 - 2 )
            cout << "FindMin or FindMax error!" << endl;

        for( i = 2; i < NUMS2; i+=2 )
            if( !tr3.contains( i ) )
                cout << "Find error1!" << endl;

        for( i = 1; i < NUMS2; i+=2 )
        {
            if( tr3.contains( i ) )
                cout << "Find error2!" << endl;
        }

        SplayTree<int> tr4;
        tr4 = tr3;

        for( i = 2; i < NUMS2;i+=2 )
            if( !tr4.contains( i ) )
                cout << "Find error1!" << endl;

        for( i = 1; i < NUMS2; i+=2 )
        {
            if( tr4.contains( i ) )
                cout << "Find error2!" << endl;
        }

        cout << "Test completed." << endl;
     AvlTree<int> tr5;
    int NUMS3 = 2000000;
    const int GAP3 =   37;

    cout << "(Avltree)Checking... (no more output means success)" << endl;

    for( i = GAP3; i != 0; i = ( i + GAP3 ) % NUMS3 )
        tr5.insert( i );
    tr5.remove( 0 );
    for( i = 1; i < NUMS3; i += 2 )
        tr5.remove( i );

    if( NUMS3 < 40 )
        tr5.printTree( );
    if( tr5.findMin( ) != 2 || tr5.findMax( ) != NUMS3 - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 2; i < NUMS3; i += 2 )
        if( !tr5.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS3; i += 2 )
    {
        if( tr5.contains( i )  )
            cout << "Find error2!" << endl;
    }

    AvlTree<int> tr6;
    tr6 = tr5;

    for( i = 2; i < NUMS3; i += 2 )
        if( !tr6.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS3; i += 2 )
    {
        if( tr6.contains( i ) )
            cout << "Find error2!" << endl;
    }

    cout << "End of test..." << endl;

      const int NEG_INF = -9999;
    RedBlackTree<int> tr7{ NEG_INF };
    int NUMS4 = 400000;
    const int GAP4  =   37;

    cout << "(RedBlackTree))Checking... (no more output means success)" << endl;

    for( i = GAP4; i != 0; i = ( i + GAP4 ) % NUMS4 )
        tr7.insert( i );

    if( NUMS4 < 40 )
        tr7.printTree( );
    if( tr7.findMin( ) != 1 || tr7.findMax( ) != NUMS4 - 1 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 1; i < NUMS4; ++i )
        if( !tr7.contains( i ) )
            cout << "Find error1!" << endl;
    if( tr7.contains( 0 ) )
        cout << "Oops!" << endl;

    
    RedBlackTree<int> tr8{ NEG_INF };
    tr8 = tr7;

    for( i = 1; i < NUMS4; ++i )
        if( !tr8.contains( i ) )
            cout << "Find error1!" << endl;
    if( tr8.contains( 0 ) )
        cout << "Oops!" << endl;

    cout << "Test complete..." << endl;
    return 0;
}



